package cn.bellychang.bobo.binarysearchtree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author ChangLiang
 * @date 2020/9/19
 */
public class BST<E extends Comparable<E>> {

    private int size;

    private Node root;

    public int size() {
        return this.size;
    }

    public void addNR(E e) {
        Node newNode = new Node();
        newNode.val = e;
        if (size == 0) {
            root = newNode;
        } else {
            // 找到parentNode 确定是它的左子树 还是 右子树
            Node parentNode = loopFindParentNode(newNode);
            if (newNode.val.compareTo(parentNode.val) < 0) {
                parentNode.left = newNode;
            } else if (newNode.val.compareTo(parentNode.val) > 0) {
                parentNode.right = newNode;
            } else {
                // 不包括重复元素
                return;
            }
        }
        size++;
    }

    public void add(E e) {
        root = doAddByRecursive(e, root);
        size++;
    }

    public boolean containsNR(E e) {
        Node temp = root;
        while (temp != null) {
            if (e.compareTo(temp.val) < 0) {
                temp = temp.left;
            } else if (e.compareTo(temp.val) > 0) {
                temp = temp.right;
            } else {
                return true;
            }
        }
        return false;
    }

    public boolean contains(E e) {
        return doContainsByRecursive(e, root);
    }

    public void preOrder() {
        doPreOrder(root);
    }

    public void inOrder() {
        doInOrder(root);
    }

    public void postOrder() {
        doPostOrder(root);
    }

    /**
     * 借助于一个栈 基于三个访问点的思路
     */
    public void preOrderNR() {
        Stack<Node> stack = new Stack();
        if (root != null) {
            System.out.println(root.val);
        }
        int count = 2;
        Node temp = root;
        while (count <= size) {
            if (temp.right != null) {
                stack.push(temp.right);
            }
            if (temp.left != null) {
                stack.push(temp.left);
            }
            Node pop = stack.pop();
            System.out.println(pop.val);
            temp = pop;
            count++;
        }
    }

    public void levelOrder() {
        Queue<Node> queue = new LinkedList();
        if (size > 0) {
            System.out.println(root.val);
        }
        Node temp = root;
        int count = 2;
        while (count <= size) {
            if (temp.left != null) {
                queue.add(temp.left);
            }
            if (temp.right != null) {
                queue.add(temp.right);
            }
            Node node = queue.remove();
            System.out.println(node.val);
            temp = node;
            count++;
        }
    }

    public E minimumNR() {
        if (size == 0) {
            throw new RuntimeException("binary search tree is empty");
        }
        Node temp = root;
        while (temp.left != null) {
            temp = temp.left;
        }
        return temp.val;
    }

    public E minimum() {
        if (size == 0) {
            throw new RuntimeException("binary search tree is empty");
        }
        return doMinimum(root);
    }

    public E maximumNR() {
        if (size == 0) {
            throw new RuntimeException("binary search tree is empty");
        }
        Node temp = root;
        while (temp.right != null) {
            temp = temp.right;
        }
        return temp.val;
    }

    public E maximum() {
        if (size == 0) {
            throw new RuntimeException("binary search tree is empty");
        }
        return doMaximum(root);
    }

    public E removeMinNR() {
        if (size == 0) {
            throw new RuntimeException("binary search tree is empty");
        }
        Node temp = root;
        if (root.left == null) {
            root = root.right;
        } else {
            Node prev = temp;
            while (temp.left != null) {
                prev = temp;
                temp = temp.left;
            }
            // 如果删除的最小节点有右子树 要连接起来
            // 如果没有 则为null
            prev.left = temp.right;
        }
        size--;
        return temp.val;
    }

    public E removeMin() {
        /*// minimum()方法中进行了binary search tree是否为空的检查
        E ret = minimum();*/

        if (size == 0) {
            throw new RuntimeException("binary search tree is empty");
        }
        // 采用搜集参数模式
        Node retNode = new Node();

        Node temp = root;
        if (root.left == null) {
            root = root.right;
            return temp.val;
        }
        root = doRemoveMin(root, retNode);
        size--;
        return retNode.val;
    }

    public E removeMaxNR() {
        if (size == 0) {
            throw new RuntimeException("binary search tree is empty");
        }
        Node temp = root;
        if (root.right == null) {
            root = root.left;
        } else {
            // root 不是最大的值 root.right有值
            Node prev = root;
            while (temp.right != null) {
                prev = temp;
                temp = temp.right;
            }
            prev.right = temp.left;
        }
        size--;
        return temp.val;
    }

    public E removeMax() {
        if (size == 0) {
            throw new RuntimeException("binary search tree is empty");
        }
        if (root.right == null) {
            Node temp = root;
            root = root.left;
            return temp.val;
        }
        Node retNode = new Node();
        root = doRemoveMax(root, retNode);
        size--;
        return retNode.val;
    }

    public void remove(E e) {
        if (size == 0) {
            throw new RuntimeException("binary search tree is empty");
        }
        // 首先找到这个Node
        // 判断其属于四种情况中的哪一种
        // 情况1 只有左子树 逻辑类似于在这棵子树上 执行removeMax
        // 情况2 只有右子树 逻辑类似于在这棵子树上 执行removeMin
        // 情况3 叶子节点 在这棵子树上 执行removeMax或removeMin都可以
        // 情况4 左右子树 需要找到此子树的前驱 RemoveMin 此前驱Node连接上此Node的左子树 和 右子树
        root = doRemove(e, root);
        size--;
    }

    private Node doRemove(E e, Node subRoot) {
        if (subRoot == null) {
            throw new RuntimeException("this element is not in the binary search tree");
        }
        // 递归终止条件
        if (subRoot.val.compareTo(e) == 0) {
            if (subRoot.left != null && subRoot.right != null) {
                // 情况4 左右子树
                Node successor = new Node();
                Node right = doRemoveMin(subRoot.right, successor);
                successor.left = subRoot.left;
                successor.right = right;
                return successor;
            } else if (subRoot.left != null) {
                // 情况1 只有左子树
                return doRemoveMax(subRoot);
            } else {
                // 情况2 和 3 只有右子树 或 叶子节点
                return doRemoveMin(subRoot);
            }
        } else if (e.compareTo(subRoot.val) < 0) {
            subRoot.left = doRemove(e, subRoot.left);
            return subRoot;
        } else {
            subRoot.right = doRemove(e, subRoot.right);
            return subRoot;
        }
    }

    private Node doRemoveMax(Node subRoot, Node retNode) {
        // 递归终止条件
        if (subRoot.right == null) {
            retNode.val = subRoot.val;
            return subRoot.left;
        }
        subRoot.right = doRemoveMax(subRoot.right, retNode);
        return subRoot;
    }

    private Node doRemoveMax(Node subRoot) {
        // 递归终止条件
        if (subRoot.right == null) {
            return subRoot.left;
        }
        subRoot.right = doRemoveMax(subRoot.right);
        return subRoot;
    }

    private Node doRemoveMin(Node subRoot, Node retNode) {
        if (subRoot.left == null) {
            // 搜集参数模式
            // 这里不能使用retNode @1462 = subRoot @1483
            // 因为局部参数无法返回 原函数中retNode仍是@1462 所以必须用set的方式
            retNode.val = subRoot.val;
            // 返回右子树
            return subRoot.right;
        }
        Node node = doRemoveMin(subRoot.left, retNode);
        subRoot.left = node;
        return subRoot;
    }

    private Node doRemoveMin(Node subRoot) {
        if (subRoot.left == null) {
            // 返回右子树
            return subRoot.right;
        }
        Node node = doRemoveMin(subRoot.left);
        subRoot.left = node;
        return subRoot;
    }

    private E doMaximum(Node subRoot) {
        // 递归终止条件
        if (subRoot.right == null) {
            return subRoot.val;
        }
        return doMaximum(subRoot.right);
    }

    private E doMinimum(Node subRoot) {
        // 递归终止条件
        if (subRoot.left == null) {
            return subRoot.val;
        }
        return doMinimum(subRoot.left);
    }

    private void doPostOrder(Node subRoot) {
        // 递归终止条件
        if (subRoot == null) {
            return;
        }
        doPostOrder(subRoot.left);
        doPostOrder(subRoot.right);
        System.out.println(subRoot.val);
    }

    private void doInOrder(Node subRoot) {
        // 递归终止条件
        if (subRoot == null) {
            return;
        }
        doInOrder(subRoot.left);
        System.out.println(subRoot.val);
        doInOrder(subRoot.right);
    }

    private void doPreOrder(Node subRoot) {
        // 递归终止条件
        if (subRoot == null) {
            return;
        }
        System.out.println(subRoot.val);
        doPreOrder(subRoot.left);
        doPreOrder(subRoot.right);
    }

    private Node loopFindParentNode(Node newNode) {
        Node temp = root;
        Node prevNode = temp;
        while (temp != null) {
            prevNode = temp;
            if (newNode.val.compareTo(temp.val) < 0) {
                temp = temp.left;
            } else if (newNode.val.compareTo(temp.val) > 0) {
                temp = temp.right;
            } else {
                break;
            }
        }
        return prevNode;
    }

    private Node doAddByRecursive(E e, Node subRoot) {
        // 递归终止条件
        if (subRoot == null) {
            Node node = new Node();
            node.val = e;
            // 与前面的上一层子树联系起来
            return node;
        }

        if (e.compareTo(subRoot.val) < 0) {
            subRoot.left = doAddByRecursive(e, subRoot.left);
        } else if (e.compareTo(subRoot.val) > 0) {
            subRoot.right = doAddByRecursive(e, subRoot.right);
        } else {
            // 不包括重复元素
        }
        return subRoot;
    }

    private boolean doContainsByRecursive(E e, Node subRoot) {
        // 递归终止条件 说明这棵子树已经遍历完成了
        if (subRoot == null) {
            return false;
        }
        if (e.compareTo(subRoot.val) == 0) {
            return true;
        } else if (e.compareTo(subRoot.val) < 0) {
            return doContainsByRecursive(e, subRoot.left);
        } else {
            return doContainsByRecursive(e, subRoot.right);
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        generateBSTString(root, 0, builder);
        return builder.toString();
    }

    /**
     * 生成以node为根节点 深度为depth的描述二叉树的字符串
     *
     * @param node
     * @param depth
     * @param res
     */
    private void generateBSTString(Node node, int depth, StringBuilder res) {
        if (node == null) {
            res.append(generateDepthString(depth) + "null\n");
            return;
        }
        // 显示当前节点
        res.append(generateDepthString(depth) + node.val + "\n");
        generateBSTString(node.left, depth + 1, res);
        generateBSTString(node.right, depth + 1, res);
    }

    /**
     * 打印深度字符串
     **/
    private String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            res.append("--");
        }
        return res.toString();
    }

    public
    class Node {
        E val;
        Node left;
        Node right;
    }
}
